package org.hot100.h200;

/**
 * @Author: wjy
 * @Date: 2022/1/12 17:26
 */
public class Solution {

    public static void main(String[] args) {

        char[][] chars = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '1'},
                {'0', '0', '0', '1', '0'}
        };

        Solution solution = new Solution();
        System.out.println(solution.numIslands4(chars));

    }

    public int numIslands(char[][] grid) {
        int count = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    /**
     * 深度优先遍历
     *
     * @param grid
     * @param r
     * @param l
     */
    public void dfs(char[][] grid, int r, int l) {
        if (r < 0 || l < 0 || r >= grid.length || l >= grid[0].length || grid[r][l] == '0') {
            return;
        }

        grid[r][l] = '0';
        dfs(grid, r, l + 1);
        dfs(grid, r, l - 1);
        dfs(grid, r + 1, l);
        dfs(grid, r - 1, l);
    }

    public int numIslands2(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs2(grid, i, j);
                }
            }
        }
        return count;
    }

    public void dfs2(char[][] nums, int m, int n) {
        if (nums[m][n] == '0' || m >= nums.length || n >= nums[0].length || m < 0 || n < 0) {
            return;
        }

        nums[m][n] = '0';
        dfs(nums, m + 1, n);
        dfs(nums, m - 1, n);
        dfs(nums, m, n + 1);
        dfs(nums, m, n - 1);
    }

    public int numIslands3(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs3(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void dfs3(char[][] nums, int m, int n) {
        if (m < 0 || n < 0 || m > nums.length || n > nums[0].length) {
            return;
        }

        nums[m][n] = '0';
        dfs3(nums, m - 1, n);
        dfs3(nums, m + 1, n);
        dfs3(nums, m, n - 1);
        dfs3(nums, m, n + 1);
    }

    public int numIslands4(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs4(grid, i, j);
                }
            }
        }
        return count;
    }

    public void dfs4(char[][] nums, int m, int n) {
        if (m < 0 || n < 0 || m >= nums.length || n >= nums[0].length || nums[m][n] == '0') {
            return;
        }

        nums[m][n] = '0';
        dfs4(nums, m + 1, n);
        dfs4(nums, m - 1, n);
        dfs4(nums, m, n + 1);
        dfs4(nums, m, n - 1);
    }
}
